COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.page frame 80 wide 72 high
C00014 ENDMK
C⊗;
.page frame 80 wide 72 high;
.DEVICE XGP;
.FONT 1 "ngr25";		<<normal font>>

Well, late again, sigh ... but, things have been happening. The LISP
conference is underway. It wll be August 24-27, 1980, immediately following
the AAAI (American Association for/of Artificial Intelligence) conference.
That conference, also held at Stanford, will run August 19-21; therefore we
expect to have optional LISP tutorials, demos,  and social events  available
on Friday and Sat. August 22-23. I have been promised  at least video tapes
and perhaps more of several maxi-class LISP machines. We also expect to have
several micro LISP "machines" available ... including my (T.(L.C)) Z-80
LISP. Hopefully other machines will be available too.

As promised last time this letter will have a bit of content: discussing
some of the implementation  details of (T.(L.C)) LISP, and design consideration
for LISP on small machines in general.

The major consideration in implementing a small LISP is the address-space.
Basically, there isn't enough.  Since most LISP objects involve pointers, and
pointers equal addresses we must try to get as many real pointers as possible.
A non-toy LISP will have many different kinds of objects. An object is a 
data item along with a collection of operations that are legal to perform
on that object. For example, a dotted pair  is an object; its legal operations
include car and cdr, but not add1; a number is an object whose legal operations
include add1 but not car and cdr. 

(T.(L.C)) LISP has about 20 different types of objects; for 
example: symbols, dotted pairs, fixnums, flonums, procedures, closures,
autoloads, and  strings.
Once you see LISP as an object-oriented
language, the implementation becomes much more tractable; the implementation
breaks into nice compact modules. Devices like the interpreter, that must
deal with objects of many different types, can be handled by having a 
"type dispatch"-table in their preamble. This scheme is  useful in the  printer and
garbage collector too. This way, if a new object is added to the system,
only moderate, and localized changes need be made; it's the difference
between sanity and chaos when writing systems.

Of course, with many different types of objects, it becomes critical that
type determination is speedy. Fortunately, this problem cooperates with another
decision we have to make: storage management. Given a data object, we need to
have some space allocated for it and its compatriots.  LISP has a "typed 
pointer architecture", meaning that from a reference to an object we must be able to
determine the type of the object. This can be accomplished in several ways (see the
Prini paper in August 1979 BYTE). Most schemes lose on a tiny machine either because
they would take too much space (add type info to every pointer), or because
they don't work well with an implementation that has a large variety of objects
(fixed memory partitions). We chose the "BIBOP" --BIg Bag Of Pages-- technique
that partitions memory into a collection of pages, and each page can contain
objects of any type subjects to the restriction that ALL objects on a 
specific page must be of the same type. In our LISP, we to 256byte pages --a
magic number for the z-80--; a "pointer" is sixteen bits, and the top byte
is used to map into the type table. The type table returns a byte representing
the type of the object reference. Thus we can have 256 different types.
The type test is reasonably fast on the z-80, since we use the alternate register
set to point to the type table. Given the type of an object, off we go to execute
the appropriate code. The scheme is fast --overall performance about 1/3 a KA-10.

As yet we have not implemented arrays, and arbitrary-precision arithmetic;
however, with the BIBOP scheme and object-oriented implementation, their addition
is straightforward. 

Begin diversion: For example, the array code needs READ, PRINT, EVAL, and
storage management code. Actually, the Read and Print code isn't crucial, but it
is always nice to supply I/O conventions that will understand constants of any
class of objects; that is a concept that most language designers overlook: I want to
point the reader at an object representing an array and make the reader internalize
it; I want to say (PRINT XX) where XX is an array and have (my choice! of) the
printed form presented. In the Eval module we need selection, construction, and
testing operations, as usual; but now we also need an updater to do (ugh bletch)
side effects. Selection, grabs an element of the array: function application
will do nicely, where the arguments are the array indices, and the array name
is the function name (indeed, that's all an array is!). Construction and
testing are trivial; only be sure that the arrary creation is dynamic! All objects
in LISP are first-class, so functions must be able to create array objects
and return them as values. Updating is only assignment. Finally for all you
APLers, we will use the LISP functionals to manufacture the APL-like operators.
Storage management is also straightforward: the allocator must be willing to
give out blocks that can store arbitrary objects as array elements, and the
garbage collector must be modified to mark the array and its elements. In total,
about a three-day mod.
End diversion:

Another key decision is how to pass parameters. At the lowest level we
pass parameters in BC DE and HL for 1, 2 and 3-argument functions. If the
procedure expects more, then ALL are passed on the stack with A containing the
actual argument count. The interpreter checks compatibility of actual and
formal parameters (but see the next paragraph).

At a higher level, we have  have followed the MIT LISP machine people and
included the Muddle-style parameter declaration mechanism. This elegant
technique makes it possible to specify quite precisely how to pass parameters
to the functions. Actual parameters are grouped as "required", "optional", and
"excess"; for details  see the Project section of Anatomy of LISP (or buy
(T.(L.C)) LISP? -- it comes with about 150 pages of documentation). 

We have also laid PROGs to rest, replacing them with a version of the LISP
machine DO, CATCH, and THROW, plus the "aux"-hack of Muddle to declare and
initialize local variables. Indeed, using these features, one can implement
PROG.

The major lackings of the system are a compiler (a subject of the next
letter, i hope) and a reasonable human interface. Currently the system
runs under CP/M using the vile RS-232 interface. A compiler is a simple --almost
micro-- diversion; the interface is a bit more difficult, but is underway
now, using a memory mapped display system; guess which one.

A final note: with this issue I've totally run out of money. So, for those of
you who supplied the initial $1.00 and wish this newsletter 
to continue and hopefully grow, I'm asking for another $1.00. 

.begin verbatim
						John Allen
						18215 Bayview Drive
						Los Gatos, Ca 95030

.end